/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-04
 * Time: 23:26
 */
import java.util.Arrays;

public class HungarianAlgorithm {

    private int n; // 图的顶点数（假设是二分图，且两边的顶点数相等）
    private int[][] graph; // 图的邻接矩阵表示，graph[i][j]表示左边第i个顶点到右边第j个顶点的权重
    private int[] lx, ly; // 分别表示左边和右边顶点的标签值
    private int[] matchX, matchY; // 分别表示左边和右边顶点的匹配关系
    private boolean[] usedY; // 记录右边顶点是否在DFS搜索中被使用过

    public HungarianAlgorithm(int[][] graph) {
        this.n = graph.length;
        this.graph = graph;
        this.lx = new int[n];
        this.ly = new int[n];
        this.matchX = new int[n];
        this.matchY = new int[n];
        this.usedY = new boolean[n];

        // 初始化标签和匹配关系
        Arrays.fill(matchX, -1);
        Arrays.fill(matchY, -1);

        // 初始化标签值（这里简单地使用最大权重作为初始标签值）
        for (int i = 0; i < n; i++) {
            lx[i] = Integer.MIN_VALUE;
            for (int j = 0; j < n; j++) {
                lx[i] = Math.max(lx[i], graph[i][j]);
            }
        }

        // 求解最大权匹配
        if (km()) {
            System.out.println("找到最大权匹配：");
            for (int i = 0; i < n; i++) {
                if (matchX[i] != -1) {
                    System.out.println("左边顶点" + i + " -> 右边顶点" + matchX[i]);
                }
            }
        } else {
            System.out.println("未找到完全匹配！");
        }
    }

    private boolean km() {
        for (int x = 0; x < n; x++) {
            Arrays.fill(usedY, false);
            if (!dfs(x)) { // 如果没有找到增广路，则修改标签值
                int delta = Integer.MAX_VALUE;
                for (int y = 0; y < n; y++) {
                    if (!usedY[y]) {
                        delta = Math.min(delta, lx[x] + ly[y] - graph[x][y]);
                    }
                }
                for (int i = 0; i < n; i++) {
                    if (matchX[i] == -1) {
                        lx[i] -= delta;
                    }
                    if (matchY[i] != -1) {
                        ly[i] += delta;
                    }
                }
            }
        }
        // 如果所有左边顶点都找到了匹配，则返回true
        for (int i = 0; i < n; i++) {
            if (matchX[i] == -1) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int x) {
        usedY[x] = true;
        for (int y = 0; y < n; y++) {
            if (graph[x][y] == lx[x] + ly[y] && !usedY[y]) {
                if (matchY[y] == -1 || dfs(matchY[y])) {
                    matchX[x] = y;
                    matchY[y] = x;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // 示例邻接矩阵（表示二分图的权重）
        int[][] graph = {
                {0, 9, 7},
                {4, 0, 5},
                {3, 8, 0}
        };

        new HungarianAlgorithm(graph);
    }
}